package gold.gold04;

import java.util.*;

/**
 * 写了个Comparator
 */
public class S1002变位词组 {

    /**
     * 核心是一个HashMap, map的key用来当set保证对string去重, 这里的key也是用了对char排序之后的String
     * map的value是一个int, 表示这个v出现的顺序, 对HashMap来说放入是无序的, 但是我们通过这个int来在ans中索引位置
     */
    public List<List<String>> groupAnagrams2(String[] strs) {
        List<List<String>> ans=new ArrayList<>();
        Map<String,Integer> hash=new HashMap<>();
        int index=0;
        for (String s:strs){
            char[] c=s.toCharArray();
            Arrays.sort(c);
            String sort_str=new String(c);
            //String sort=String.copyValueOf(c);
            if(!hash.containsKey(sort_str)){
                hash.put(sort_str,index++);
                List<String> l=new ArrayList<>();
                l.add(s);
                ans.add(l);
            }else ans.get(hash.get(sort_str)).add(s);
        }
        return  ans;
    }

    /**
     * 15, 先给每个String打个标签, 就是自己排序的结果 "adc" -> "acd" 这样。然后根据这个标签排序, 这样的话变位词就在一起了
     * 然后循环把在一起的变位词写入新的List里。在List的遍历中操作List(增删)还是比较危险的。
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs == null || strs.length == 0) return new LinkedList<List<String>>();
        List<List<String>> result = new ArrayList<>();
        char[] tempCharList;
        for(String s : strs){
            tempCharList = s.toCharArray();
            Arrays.sort(tempCharList);
            List<String> tempStringList = new LinkedList<>();
            // 把s的排序结果和s放在一个链表里
            tempStringList.add(new String(tempCharList));
            tempStringList.add(s);
            result.add(tempStringList);
        }
        Collections.sort(result, (List<String> x, List<String> y)->{
            return (x.get(0)).compareTo(y.get(0));
        });
        // 迭代然后整理, 把别的List<String>里的东西写到result上, 有读有写,
        // 不知道怎么处理, 而且有可能会有集合迭代常出现的那种"修改"问题。
        // 不如造一个新result, 往里面写
        String tempLate = result.get(0).get(0);
        List<List<String>> result2 = new ArrayList<>();
        result2.add(new LinkedList<String>());
        for(List<String> temp1: result){
            if(!temp1.get(0).equals(tempLate)){
                tempLate = temp1.get(0);
                result2.add(new LinkedList<String>());
            }
            result2.get(result2.size() - 1).add(temp1.get(1));
        }
        return result2;
    }
}
